package com.sevent;

import java.util.ArrayList;

//public class com.sevent.全排列 {
//    ArrayList<String> res = new ArrayList<>();
//    int count = 0;
//
//    public ArrayList<String> getPermutation(String A){
//        char [] arr = A.toCharArray();
//        //Arrays.sort(arr);
//        getPermutationCore(arr,0);
//        return res;
//    }
//
//    public void getPermutationCore(char[] arr, int k) {
//        if (k == arr.length) {
//            res.add(new String(arr));
//        }
//
//        count ++;
//        for (int i = k; i < arr.length; i++) {
//            System.out.println("这是第" + count +"次循环了，现在的arr是" + new String(arr) + ",现在的k是，i是" + k + ","+i);
//            swap(arr, k, i);
//            getPermutationCore(arr, k + 1);
//            swap(arr, k, i);
//        }
//    }
//
//    public void swap(char[] arr, int i, int j) {
//        char tmp = arr[i];
//        arr[i] = arr[j];
//        arr[j] = tmp;
//    }
//
//    public static void main(String[] args) {
//        ArrayList<String> res = new com.sevent.全排列().getPermutation("abc");
//        System.out.println(res);
//    }
//}

public class 全排列 {
    ArrayList<String> res = new ArrayList<>();

    public static void main(String[] args) {
        ArrayList<String> res = new 全排列().getPermutation("000000011111");
        System.out.println(res);
    }

    public boolean isSame(char[] arr, int first, int end) {
        for (int i = first; i < end; i++) {
            if (arr[i] == arr[end]) {
                return false;
            }
        }
        return true;
    }

    public ArrayList<String> getPermutation(String A) {
        char[] arr = A.toCharArray();
        getPermutationCore(arr, 0);
        return res;
    }

    public void getPermutationCore(char[] arr, int k) {
        if (k == arr.length) {
            res.add(new String(arr));
        }

        for (int i = k; i < arr.length; i++) {
            if (isSame(arr, k, i)) {
                swap(arr, k, i);
                getPermutationCore(arr, k + 1);
                swap(arr, k, i); // 回溯
            }
        }
    }

    public void swap(char[] arr, int k, int i) {
        char tem = arr[k];
        arr[k] = arr[i];
        arr[i] = tem;
    }


}